package datastructure.structure;


import java.util.NoSuchElementException;

/**
 * 二叉平衡树
 * @author or2
 * @date 2021/7/28 15:50
 */
public class BST<E extends Comparable<E>>{

    private Node root;

    private int size;

    public BST() {
        this.root = null;
        this.size = 0;
    }

    /**
     * 递归方式添加新元素
     * @param value 结点的值
     */
    public void add(E value) {
        if (this.root == null) {
            this.root = new Node(value);
            this.size++;
        } else {
            addRecursion(root, value);
        }
    }

    /**
     * 非递归添加结点
     * @param value 新元素的值
     */
    public void addNonRecursive(E value) {
        if (this.root == null) {
            this.root = new Node(value);
            this.size++;
        }

        Node p = root;
        Node parentP = null;

        while (p != null) {
            int compareTo = value.compareTo(p.value);
            parentP = p;
            if (compareTo < 0) {
                p = p.lNode;
            } else if (compareTo > 0) {
                p = p.rNode;
//            不允许值相同
            } else {
                return;
            }
        }
        
        Node node = new Node(value);
        if (value.compareTo(parentP.value) < 0) {
            parentP.lNode = node;
        } else {
            parentP.rNode = node;
        }

        size++;
    }

    /**
     * 递归算法: 向根为 root 的结点添加新元素
     * @param root 开始的结点
     * @param value 新元素的值
     */
    private void addRecursion(Node root, E value) {
        int compareTo = value.compareTo(root.value);
        if (compareTo == 0) {
            return;
        } else if (compareTo < 0 && root.lNode == null) {
            root.lNode = new Node(value);
            size++;
            return;
        } else if (compareTo > 0 && root.rNode == null) {
            root.rNode = new Node(value);
            size++;
            return;
        }

        if (compareTo < 0) {
            addRecursion(root.lNode, value);
        } else {
            addRecursion(root.rNode, value);
        }
    }

    /**
     * 检测是否存在某元素值
     * @param value 检测树中是否存在该值
     * @return 有->true<br/>没有->false
     */
    public boolean contain(E value) {
        Node p = root;
        while (p != null) {
            int compareTo = value.compareTo(p.value);
            if (compareTo == 0) {
                return true;
            } else if (compareTo < 0) {
                p = p.lNode;
            } else {
                p = p.rNode;
            }
        }

        return false;
    }

    public void preOrder() {
        preOrder(root);
    }

    /**
     * 前序遍历BST
     * @param root 开始遍历的根节点
     */
    private void preOrder(Node root) {

        if (root == null) {
            return;
        }

        preOrder(root.lNode);
        preOrder(root.rNode);
    }

    /**
     * 查找该树最小元素
     * @return <E> 最小元素的值
     */
    public E minimums() {
        if (root == null) {
            throw new NoSuchElementException("该树为空, 不存在最小元素");
        }

        Node p = root;
        while (p.lNode != null) {
            p = p.lNode;
        }
        return p.value;
    }

    /**
     * 删除最小结点
     * @return 被删除的结点的值
     */
    public E removeMin() {
        if (root == null) {
            throw new NoSuchElementException("该树为空, 不存在最小元素");
        }
//        只有根节点
        if (root.lNode == null) {
            root = null;
            size = 0;
        }
//        找到最小结点
        Node p = root;
        Node pParent = null;
        while (p.lNode != null) {
            pParent = p;
            p = p.lNode;
        }

/*        assert pParent != null;
          删除最小结点    */
        size--;
        if (p.rNode == null) {
            pParent.lNode = null;
        }
        pParent.lNode = p.rNode;
        p.rNode = null;

        return p.value;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 树结点
     */
    private class Node {

        private E value;
        private Node lNode, rNode;

        public Node(E value) {
            this.value = value;
            this.lNode = null;
            this.rNode = null;
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        int leafNodesNum = (int)( Math.pow(2, Math.log(size) / Math.log(2)) );

        generateString(root, 0, stringBuilder, leafNodesNum);

        return stringBuilder.toString();
    }

    /**
     * 生成方便观看的BST
     * @param root 当前结点做根节点, 不断递归
     * @param depth 当前深度, 每次递归 +1
     * @param stringBuilder 拼接字符串用
     * @param leafNodesNum 防止重复计算, 第一次计算后一直传递
     */
    private void generateString(Node root, int depth, StringBuilder stringBuilder, int leafNodesNum) {
        double section = Math.pow(2, depth) + 1;
        int sectionLength = (int) (leafNodesNum / section);
        String gap = "\t".repeat(sectionLength);

        if (root == null) {
            stringBuilder.append(gap).append("空").append("\n");
            return;
        }

        generateString(root.lNode, depth + 1, stringBuilder, leafNodesNum);
        stringBuilder.append(gap).append(root.value).append("\n");
        generateString(root.rNode, depth + 1, stringBuilder, leafNodesNum);
    }
}
